import math

def factors(x):
	f = []	
	i = 2
	while i <= x:
		if x % i == 0:
			x = int(x / i)
			f.append(i)
		else:
			i += 1
	
	return f

def isPrime(x):
	i = 2
	result = True
	while i <= math.sqrt(x):
		if x % i == 0:
			result = False
			break
		if i == 2:
			i =3
		else:
			i += 2
		
	return result

def sieve(x):
	numbers = list(range(x+1))
	numbers[1] = 0
	
	primes = []
	prime = 2
	while prime < x:
		primes.append(prime)
		for r in range(prime+prime, x, prime):
			numbers[r] = 0
		
		prime += 1
		while prime < x and numbers[prime] == 0:
			prime += 1
			
		
	return primes
